Whole program paths

Abstract

Whole program paths (WPP) are a new approach to capturing and representing a program's dynamic---actually executed---control flow. Unlike other path profiling techniques, which record intraprocedural or acyclic paths, WPPs produce a single, compact description of a program's entire control flow, including loop iteration and interprocedural paths.This paper explains how to collect and represent WPPs. It also shows how to use WPPs to find hot subpaths, which are the heavily executed sequences of code that should be the focus of performance tuning and compiler optimization.

References

1. 1 G. Ammons, T. Ball, and J. R. Larus, "Exploiting Hardware Performance Counters with Flow and Context Sensitive Profiling," in Proceedings of the SIGPLAN '97 Conference on Programming Language Design and Implementation. Las Vegas, NV, 1997, pp. 85-96.
2. 2 G. Ammons and J. R. Larus, "Improving Data-flow Analysis with Path Profiles," in Proceedings of the SiGPLAN '98 Conference on Programming Language Design and Implementation. Montreal, Canada, 1998, pp. 72-84.
3. 3 S. Andler, "Predicate Path Expressions," in Proceedings of the Sixth Annual A CM Symposium on Principles of Programming Languages. San Antonio, Texas, 1979, pp. 226-236.
4. 4 B. S. Baker, "Parametefized Duplication in Strings: Algorithms and an Application to Software Maintenance," SIAM Journal of Computing, vol. 26, pp. 1343-I 362, 1995.
5. 5 V. Bala, "Low Overhead Path Profiling," Hewlett Packard Labs 1996.
6. 6 T. Ball and J. R. Larus, "Efficient Path Profiling," in Proceedings of the 29th Annual iEEEdACM International Symposium on Microarchitecture. Paris, France, 1996, pp. 46-57.
7. 7 T. Ball, P. Mataga, and M. Sagiv, "Edge Profiling Versus Path Profiling: the Showdown," in Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. San Diego, CA, 1998, pp. 134- 148.
8. 8 R. Bodik, R. Gupta, and M. L. Sofia, "Refining Data Flow Information using Infeasible Paths," in Proceedings of the A CM SIGSOFT Fifth Symposium on the Foundations of Software Engineering. Zurich, Switzerland, 1997.
9. 9 I.-C. K. Chen, J. T. Coffey, and T. N. Mudge, "Analysis of Branch Prediction via Data Compression," in Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems. Cambridge, MA, 1996, pp. 128-137.
10. 10 E. N. Clarke, E. A. Emerson, and A. P. Sistla, "Automatic Verification of Finite-State Concurrent Systems Using Temporal Logic Specifications," A CM Transactions on Programming Languages and Systems, vol. 8, pp. 244-263, 1986.
11. 11 J. A. Fisher, "Trace Scheduling: A Technique for Global Microeode Compaction," IEEE Transactions on Computers, vol. C-30, pp. 478-490, 1981.
12. 12 J. A. Fisher, J. R. Ellis, J. C. Ruttenber g, and A. Nicolau, "Parallel Processing: A Smart Compiler and a Dumb Machine," in Proceedings of the A CM SiGPLAN '84 Symposium on Compiler Construction. Montreal, Canada, 1984, pp. 37-47.
13. 13 J. Gray, "The Benchmark Handbook for Database and Transaction Processing Systems," in The Morgan Kaufmann Series in Data Management Systems, J. Gray, Ed., second ed. San Francisco: Morgan Kaufmann, 1993.
14. 14 R. Gupta, D. A. Berson, and J. Z. Fang, "Path Profile Guided Partial Dead Code Elimination Using Predication," in Proceedings of the International Conference on Parallel Architecture and Compilation Techniques (PACT). San Francisco, CA, 1997.
15. 15 Q. Jacobson, E. Rotenberg, and J. E. Smith, "Path-Based Next Trace Prediction," in Proceedings of the 30th Annual IEEE/ACM International Symposium on Microarchitecture. Research Triangle Park, NC, 1997.
16. 16 J. R. Larus, "Abstract Execution: A Technique for Efficiently Tracing Programs," Software--Practice and Experience, vol. 20, pp. 1241-1258, 1990.
17. 17 J. R. Larus and E. Schnarr, "EEL: Machine-independent Executable Editing," in Proceedings of the SiGPLAN '95 Conference on Programming Language Design and Implementation. La Jolla, CA, 1995, pp. 291-300.
18. 18 D. Melski and T. Reps, "Interprocedural Path Profiling," Computer Sciences Department, University of Wisconsin- Madison, Technical Report TR- 1382, September 1998.
19. 19 D. Melski and T. Reps, "Interprocedural Path Profiling," in Proceedings of CC '99: 8th International Conference on Compiler Construction. Amsterdam, The Netherlands, 1999.
20. 20 D. Mosberger and L. L. Peterson, "Making Paths Explicit in the Scout Operating System," in Proceedings of the Second USENIX Symposium on Operating Systems Design and Implementation (OSDI). Seattle, WA, 1996, pp. 153-167.
21. 21 C. G. Nevill-Manning and I. H. Witten, "Compression and explanation using hierarchical grammars," The Computer Journal, vol. 40, pp. 103-116, 1997.
22. 22 C. G. Nevill-Manning and I. H. Witten, "Linear-time, incremental hierarchy inference for compression," in Proceedings of the Data Compression Conference (DCC '97). Snowbird, UT: iEEE Computer Society, 1997, pp. 3-1 I.
23. 23 A. R. Pleszkun, "Techniques for Compressing Program Address Traces," in Proceedings of the 27th Annual IEEE/A CM International Symposium on Mi croarchitecture, 1994, pp. 32-40.
24. 24 C. Pu, T. Autrey, A. Black, C. Consel, C. Cowan, J. Inouye, L. Kethana, J. Walpole, and K. Zhang, "Optimistic Incremental Specialization: Streamlining a Commercial Operating System," in Proceedings of the Fifteenth A CM Symposium on Operating System Principles. Copper Mountaint Resort, CO, 1995, pp. 314-324.
25. 25 E. Rotenberg, S. Bennett, and J. E. Smith, "Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching," in Proceedings of the 29th Annual IEEE/ACM International Symposium on Microarchitecture. Paris, France, ! 996, pp. 24-34.
26. 26 E. Rotenberg, Q. Jacobson, Y. Sazeides, and J. Smith, "Trace Processors," in Proceedings of the 30th Annual iEEE/A CM International Symposium on Microarchitecture. Research Triangle Park, NC, 1997, pp. 138-148.
27. 27 A. Srivastava and A. Eustace, "ATOM A System for Building Customized Program Analysis Tools," in Proceedings of the SIGPLAN '94 Conference on Programming Language Design and Implementation. Orlando, FL, 1994, pp. 196-205.
28. 28 C. Young, N. Gloy, and M. D. Smith, "A Comparative Analysis of Schemes for Correlated Branch Prediction," in Proceedings of the 22nd Annual International Symposium on Computer Architecture, 1995, pp. 276-286.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Metrics

• Information systems

  • Data management systems

    • Data structures

      • Data layout

        • Data compression

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Paths and connectivity problems

• Software and its engineering

  • Software notations and tools

    • Compilers